package com.itzmn.datastructure.newcode;

import java.util.HashMap;

/**
 * @Author: 张梦楠
 * @Date: 2019/1/2 17:09
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description:  前缀树
 *
 * 是一颗树。
 *
 * 添加字符串的时候，比如‘abc’
 *
 * 会从根节点，开始判断是否有一条节点的路是a，没有，新建一个节点，路是a，然后从a开始
 * ，判断是否有一个指向节点的路是b，然后同理，再次添加字符串的时候，也是从根节点开始判断。然后就形成了多叉树
 *
 * 用处
 * 有多少某个前缀的字符串。查是否存过某个字符串，
 *
 * 在节点中，存储这条路经过的次数，和是否是结尾。可以很好的判断
 */
public class TrieTree {


    public class TreeNode{
        /**
         *
         * 多少次从这个节点经过
         */
        int path;
        /**
         *
         * 多少个以这个为结尾
         */
        int end;

        /**
         *  表示这个节点有多少条路，对应节点。
         *  key表示路的值
         *  value表示路的节点
         */
        HashMap<Character,TreeNode> nexts;
    }


    /**
     * 树根
     */
    public TreeNode root;
    TrieTree(){

        root = new TreeNode();
    }


    /**
     * 添加字符串
     * @param word
     */
    public void insert(String word){

        char[] chars = word.toCharArray();
        TreeNode root = this.root;
        for (int i=0; i<chars.length; i++){
            if (! root.nexts.containsKey(chars[i])) {
                TreeNode treeNode = new TreeNode();
                root.nexts.put(chars[i], treeNode);
            }
            root.path++;
            root = root.nexts.get(chars[i]);
        }

        // 当全部添加完,将最后一个节点的结束标志加一
        root.end++;
    }

    /**
     * 查找字符串添加次数
     * @param word
     * @return
     */
    public int serachNum(String word){

        if (word == null || word.trim().equals("")){
            return 0;
        }

        TreeNode root = this.root;

        char[] chars = word.toCharArray();
        for (int i=0; i<chars.length; i++){
            if (root.nexts.containsKey(chars[i])){
                root = root.nexts.get(chars[i]);
            }else {
                return 0;
            }
        }

        return root.end;

    }

    /**
     * 删除字符串
     * @param word
     */
    public void delete(String word){

        // 判断是否添加过该字符串
        if (serachNum(word) == 0){
            return;
        }

        TreeNode root = this.root;

        char[] chars = word.toCharArray();
        for (int i=0; i<chars.length; i++){
            TreeNode treeNode = root.nexts.get(chars[i]);
            // 如果当前节点删除一次后就没了，那么后面就直接挂null，
            if (--treeNode.path == 0){
                root.nexts.put(chars[i],null);
                return;
            }
            root = treeNode;
        }
        // 如果这个字符串到这个节点结束，吧结束标志减一
        root.end--;
    }

    /**
     * 判断以该字符串开头的字符串有多少
     * @param word
     * @return
     */
    public int prefixStr(String word){

        char[] chars = word.toCharArray();

        TreeNode root = this.root;
        for (int i=0; i<chars.length; i++){
            if (root.nexts.containsKey(chars[i])){
                root = root.nexts.get(chars[i]);
            }else {
                return 0;
            }
        }

        return root.path;
    }






}
